Recently, the amount of information to be handled in various fields has been increasing at an explosive rate. In some fields, the amount of information has reached the order of gigabytes to terabytes, and such a huge amount of data is making it increasingly difficult to quickly retrieve desired data from a data source.
Pattern matching, a technique for searching for a particular pattern from within given text, is employed in a variety of fields including word processing software and database searches.
Specifically, the demand for applications such as XML databases that performs pattern matching (searching) for processing has been increasing in recent years and, to address this trend, there is proposed a technique in which an automaton matching device (search core) that performs pattern matching is incorporated in a processor in order to enhance the processing speed.
In the prior art, a study has been made on how fast the matching of a piece of text may be accomplished using a processor system having a plurality of matching devices.
For example, when performing matching (searching) operations in an XML database system in which the database is constructed directly from a plurality of XML text groups, if pattern matching is performed from the beginning, since there is a high degree of parallelism between each XML text the processing speed may be easily enhanced by processing the matching operations in parallel, for example, by increasing the number of matching devices. However, this increases the amount of postprocessing that the CPU performs using the results of the matching.
Further, when performing the matching process in parallel with the postprocessing by the CPU, a data transfer method and a control method for reducing the overhead involved in the parallel processing become important in order to enhance the speed of the search (matching) system as a whole.
It also becomes preferable to provide a mechanism for performing the postprocessing by the CPU while retaining the text-by-text order relationship between the matching results. For example, when performing search operations in the XML database system, if the order in which the XML text is processed by the CPU differs each time from that managed by the XML database, the search results will be presented in a different order each time, impairing the usability of the system.
There is therefore a need to provide an efficient mechanism that may process the results of the matching in parallel after the results of the matching completed in a random order through parallel processing have been made ready for postprocessing in the order of the records.
In the prior art, there is proposed a method that performs the matching of a plurality of characters at a time by using a processor system having a plurality of matching devices.
There is also proposed in the prior art a method that divides the text to be matched against in order to perform parallel processing by using a processor system having a plurality of matching devices.    Patent Document 1: Japanese Laid-open Patent Publication No. 2005-242672    Patent Document 2: Japanese Patent No. 2865831 (Japanese Laid-open Patent Publication No. H04-111064)